package 排序算法;

import java.util.ArrayList;
import java.util.List;

public class 希尔排序 {
    static Integer[] arrays = {1, 56, 32, 56, 12, 77, 88, 21};

    public static void main(String[] args) {

        //生成步长序列
        List<Integer> stepList = shellStep();
        //逐步拆分成列，再对每一列进行插入排序
        for (Integer integer : stepList) {
            sort(integer);
        }

        for (int i = 0; i < arrays.length; i++) {
            System.out.print(arrays[i] + "_");
        }
    }

    private static void sort(Integer step) {
        for (int col = 0; col < step; col++) {
            for (int begin = col + step; begin < arrays.length; begin += step) {
                int cur = begin;
                while (cur > col && arrays[cur] < arrays[cur - step]) {
                    int tmp = arrays[cur - step];
                    arrays[cur - step] = arrays[cur];
                    arrays[cur] = tmp;
                    cur -= step;
                }
            }
        }
    }

    private static List<Integer> shellStep() {
        List<Integer> stepList = new ArrayList<>();
        int step = arrays.length;
        while ((step = step >> 1) > 0) {
            stepList.add(step);
        }
        return stepList;

    }

}
